package leetcode;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * Created by Ghost on 2014/11/6.
 */
public class Merge_k_Sorted_Lists {
    public ListNode mergeKLists(List<ListNode> lists){
        if(lists==null || lists.size()==0)
            return null;
        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.size(),new Comparator<ListNode>(){

            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }

        });

        for(ListNode ln:lists){
            if(ln!=null)
                pq.add(ln);
        }

        ListNode head = new ListNode(0);
        ListNode h = head;
        while(!pq.isEmpty()){
            ListNode tmp = pq.poll();
            head.next = tmp;
            if(tmp.next!=null)
                pq.add(tmp.next);
            head = head.next;
        }
        return h.next;
    }
    public static void main(String[] args){
        List<ListNode> lists = new ArrayList<ListNode>();
        lists.add(null);
        Merge_k_Sorted_Lists merge_k_list = new Merge_k_Sorted_Lists();
        merge_k_list.mergeKLists(lists);
        System.out.println(lists);
    }
}
